#include "../include/dp.h"

Result dp_knapsack(Item* items, int n, int capacity) {
    Result result = {0};
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);

    // 分配内存
    double** dp = (double**)malloc((n + 1) * sizeof(double*));
    int** path = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (double*)malloc((capacity + 1) * sizeof(double));
        path[i] = (int*)malloc((capacity + 1) * sizeof(int));
    }

    // 初始化
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            dp[i][j] = 0;
            path[i][j] = 0;
        }
    }

    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (items[i-1].weight <= j) {
                double value_with_item = dp[i-1][j-items[i-1].weight] + items[i-1].value;
                if (value_with_item > dp[i-1][j]) {
                    dp[i][j] = value_with_item;
                    path[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j];
                    path[i][j] = 0;
                }
            } else {
                dp[i][j] = dp[i-1][j];
                path[i][j] = 0;
            }
        }
    }

    // 回溯找出选中的物品
    result.selected_items = (int*)malloc(n * sizeof(int));
    int current_capacity = capacity;
    result.selected_count = 0;

    for (int i = n; i > 0; i--) {
        if (path[i][current_capacity]) {
            result.selected_items[result.selected_count++] = items[i-1].id;
            current_capacity -= items[i-1].weight;
        }
    }

    result.total_value = dp[n][capacity];

    // 释放内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
        free(path[i]);
    }
    free(dp);
    free(path);

    // 计算执行时间
    QueryPerformanceCounter(&end);
    result.time_taken = (double)(end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;

    // 计算内存使用
    result.memory_used = sizeof(Result) + n * sizeof(int) + 
                        (n + 1) * (capacity + 1) * (sizeof(double) + sizeof(int));

    return result;
} 